Representableのinstance例: Stream a

Representable型クラスのinstanceの例としてStream a型を考える

Stream a型の定義

code:hs

data Stream a = Cons a (Stream a)

これはData.Streamでも提供されている

Stream a型の意味

まず身近なList型がどういうものだったかを思い出す

code:hs

data List a = Nil | Cons a (List a)

比較して見ると、Stream aは、Nilの無いListと捉えることができる

これは以下のことを意味する

空になり得ない

終端がない

だから、Stream aは無限リストを表している型だということがわかる

実際、Data.Stream moduleを見れば、Listに関する関数と似たものが提供されていることがわかる

Stream a型をRepresentableのinstanceにする

準備としてFunctorである必要があるのでderivingしておく

code:hs

{-# LANGUAGE DeriveFunctor #-}

data Stream a = Cons a (Stream a) deriving (Functor, Show)

定義

code:hs

instance Representable Stream where

type Rep Stream = Integer

index (Cons x _) 0 = x

index (Cons _ xs) n = index xs (n-1)

tabulate int2x = go 0

where go n = Cons (int2x n) (go (n+1))

positionsで定義するなら

code:hs

instance Representable Stream where

type Rep Stream = Integer

index (Cons x _) 0 = x

index (Cons _ xs) n = index xs (n-1)

positions = fix $ \xs -> Cons 0 (fmap (+1) xs)

RepresentableなStream aのプログラミング的な意味

関数indexは、

与えられたStream aに対し、

位置(いわゆるインデックス)nに対応する要素xを返す

具体化した型を見ればわかりやすい

index :: Stream a -> Integer -> a

関数tabulateは、

「位置nに対応する要素xを返す」関数から

Stream aを生成する

具体化した型を見ればわかりやすい

tabulate :: (Integer -> a) -> Stream a

与えられた規則に則った無限列を作る関数ってことだねmrsekut.icon

tabulate :: 規則 -> 無限列

関数positionsは、

型はStream Intger

インデックス側の無限リストを表す

index, tabulate, positionsの使用例は後述

RepresentableなStream aの圏論的な意味

表現可能関手とRepresentable型クラスの関係を思い出す

Stream aが、Representableであるということは

Stream aと、(Integer -> a)が自然同型であるということを意味する

このIntegerは、instance定義のtype Rep Stream = Integerから来ているmrsekut.icon

つまり、Stream aの全要素に一対一対応するように関数(Integer -> a)が存在する

Stream aが無限列であることと、Integerのinhabitantが無限個あることの関連が見えてくるmrsekut.icon

具体例Stream Int

各要素がIntな無限列を考える

例えば[0,0,0,0,...]という無限リスト

code:hs

zeros :: Stream Int

zeros = Cons 0 zeros

例えば[0,1,2,3,...]という無限リスト

code:hs

nats :: Stream Int

nats = let go n = Cons n (go (n+1)) in go 0

こういう各Stream Intな無限列に対して、関数Integer -> Intが一対一対応する

https://gyazo.com/0e4a9fc8fec0e4ff138d066e3b0c954b

この図中の関数は

f = idnex zeros

g = index nats

のことである

indexの使用例を見ておこう

特に面白くもないが、100番目の要素を確認する例

code:ghci

index zeros 100

index nats 100

100

tabulateを使って、zerosやnats以外の例を生成してみよう

無限列はログとして表示できないので、先頭のn個を取って通常のListとして返す関数を用意しておく

code:hs

import Prelude hiding (take)

take :: Int -> Stream a -> a

take n ~(SCons x xs)

| n == 0 = []

| n > 0 = x : take (n - 1) xs

| otherwise = error "Stream.take: negative argument."

Data.Streamから取ってきた。

中身はそこまで気にする必要はない

例として[0,10,20,30,...]のようなStreamを作ってみる

code:hs

tenNats = tabulate $ \i -> i*10

takeを使って確認してみる

code:ghci

take 5 tenNats

0,10,20,30,40

同様にして上述のzerosやnatsも、tabulateで定義できる

code:hs

zeros = tabulate $ const 0

nats = tabulate fromIntegral

postisionsはインデックスの無限リストを表す

これもtakeと併せて使うと

code:ghci

take 5 positions

0,1,2,3,4

これはnatsと見た目は同じだが、型が異なる

natsの型は、Stream Intだが、

positionsの型は、aによらずStream Integerである

これはinstanceの定義時に決まる

表現可能関手とRepresentable型クラスの表記をしてみる

https://gyazo.com/3ecdd03f2ed84fa3fd3a2f564206b809

これを見てなにかすごい知見が得られるかといえば全然そんなことない気がするmrsekut.icon

一応補足しておくと、

表現可能関手を考える際に重要になってくる2つのパラメータは、今回はStream関手と、Integer対象だった

IntegerからのHomを考える際に今回は例としてInt対象に着目した

b'対象は何でも良いし、今回は見ていないので開けたままにしている

Representableの文脈でStream型を解説している記事

Representable Functors: Practical Examples | WorksHub

Cats の表現可能関手 Representable を調べてみる - Qiita

Scala

Representable Functors | Bartosz Milewski's Programming Cafe

表現可能関手 - bitterharvest’s diary